package jun;

import java.lang.reflect.Array;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-16 11:11
 * @description：
 * @modified By：
 * @version:
 */
public class Jun16 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/solution/shi-jian-fu-za-du-o2k-kong-jian-fu-za-du-o1-by-qi-/ 1423. 可获得的最大点数
     1. 首先先求出数组的前缀和 s[2] = s[0]+s[1]+s[2]
     2. 每一回合我们去掉左边的一个数 加上后面右边的一个数字 每次取最大值一直到k
     * create time: 2020-6-16 11:21
     * @params [cardPoints, k]
     * @return int
     */
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length, res=0;
        int[] s = new int[n+1];
        for(int i=0;i<n;i++){
            s[i+1] = s[i] + cardPoints[i];
        }
        for(int i=0;i<=k;i++){
            res = Math.max(res, s[i] + s[n] - s[n-k+i]);
        }
        return res;
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/ 面试题47. 礼物的最大价值
     * 其实就是迷宫题
     * 每一步的最大值取决于他的上一格和左一格
     * create time: 2020-6-16 11:29
     * @params [grid]
     * @return int
     */
    public int maxValue(int[][] grid) {
        //初始化第一行
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid[0].length ; i++) {
            dp[0][i] = dp[0][i-1]+grid[0][i];
        }
        //初始化第一列
        for (int i = 1; i < grid.length; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[i].length; j++) {
                dp[i][j] = grid[i][j]+Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}
